In digital data systems, it is common for data stored in memory as well as data transmitted over a communications channel to be corrupted by errors. There are numerous techniques typically employed to detect errors and/or correct detected errors. One example of an error detection technique is the well known cyclic redundancy code (CRC) check. Other techniques that use block codes and convolutional codes permit both error detection and error correction. For error detection and correction, additional coding bits are added to the data bits. When the data is received over the communications channel or retrieved from memory, the received/retrieved data are decoded using the additional bits in some fashion to detect if some of the data are in error. One way of thinking of these decoding procedures is to analogize them to a human's ability to correct spelling errors while reading printed text. Because words are sufficiently different from each other, the reader intuitively knows which word is meant.
These error detection and/or correction coding techniques all add, to some degree, redundant information. The more redundancy built into a unit of data, the more likely that errors can be accurately detected, and in some instances, corrected. Unfortunately, as the number of coding/redundant bits increases, the overall data "throughput" decreases. In other words, the actual data content transmitted per unit time is reduced. Additionally, as the number of coding/redundancy bits increases, the complexity of the encoding/decoding algorithms increases which consumes limited data processing resources and slows down data processing time.
In some relatively "clean" environments where data are unlikely to be corrupted, fewer coding/redundancy bits can be used in conjunction with simpler error detection and/or correction procedures. However, in hostile environments where there is considerable noise, interference, etc., such simplification is usually not an option. Consider for example a radio/wireless communications environment. The radio frequency communications channel is subjected to a barrage of corrupting factors including ever present noise, nearly continuously changing communications channel characteristics, multipath fading, time dispersion which causes intersymbol interference (ISI), interference from adjacent channel communications, and a host of other factors.
One communications protocol (i.e., procedure) used to protect against these various corrupting factors is automatic repeat request (ARQ) transaction processing. A pure ARQ system employs only error detection--error correction is not used. More specifically, data packets having some type of error detection bits/coding are transmitted from a sender to a receiver over a communications channel. Each received data packet is processed by the receiver using the error detection bits included in the data packet to determine if the data packet was received correctly. If the packet was safely and accurately received, the receiver transmits an acknowledgment signal (ACK) back to the sender. If errors are detected, the receiver sends a negative acknowledgment (NAK) back to the sender, discards the data packet, and waits for a retransmission of that same data packet from the sender. In addition, a predetermined timing window is set to allow the sender sufficient time to transmit information, the receiver to receive and process the information, and then transmit an ACK or NAK signal to the sender. If the sender does not receive an ACK signal within that predetermined window or if it receives a NAK signal during the window, the sender retransmits the data packet.
In a noisy or otherwise data corrupting environment like wireless communications, a large number of retransmissions may occur before data is correctly received. Significantly, no matter how many times a data packet is transmitted/retransmitted, the receiver does not become any "smarter" about how to decode the correct information from a later retransmitted data packet In other words, the probability of receiving the packet correctly on any given data packet retransmission is no better than the probability of the previous retransmission of that packet.
One possible option for improving this ARQ protocol is to add forward error correction (FEC) bits to the data packet to permit some degree of bit correction. An example of such a "hybrid" technique would be to replace CRC error detection bits with Bose-Chaudhuri-Hocquenghem (BCH) parity check bits. If erroneous bits could be corrected by the receiver, an acknowledgment could be sent to the transmitter without the need for further retransmission. Even using such a hybrid technique where a limited number of error patterns can be corrected, such a hybrid technique (like the pure ARQ protocol) does not make use of the information contained in the previously received packets. Erroneous data packets in the pure ARQ protocol or data packets having errors uncorrectable using the hybrid technique are simply discarded requiring a continuing sequence of retransmissions.
What is needed is a data recovery technique applicable for example to ARQ protocols which makes use of information contained in previously transmitted packets, i.e., using erroneous data packets rather than discarding them, so that the currently received retransmission of the data packet can be corrected using that information from the previously received data packets. Many of the bits of the earlier transmitted packets are likely to be correct, and only one or a few of the bits in most instances are corrupted. A main objective of this invention is to utilize the correct information accumulated from prior transmissions of the packet to generate a correct data packet. Such a technique should not, however, consume too much processing time and should minimize, if possible, the amount of memory required for such processing so that the technique can be used in various environments where memory resources are limited, e.g., portable/mobile radios. It would be desirable therefore to have forward error correction in an ARQ protocol without requiring the addition of forward error correction bits to each data packet.
It is an object of the present invention to provide a data recovery system in which a correct data unit is recovered using information contained in previously received/transmitted but unacceptable data units.
It is an object of the present invention to provide such a data recovery technique in an automatic repeat request (ARQ) transaction environment so that data can be corrected without having to add additional forward error correction bits to the data units.
It is a further object of the invention to provide an error recovery technique which is effective in recovering data in a hostile environment without requiring the addition of forward error correction bits to the data packet, complex forward error data correction decoding procedures, or significant memory resources.
The present invention solves the various problems noted above and meets these and other objectives. In an automatic repeat request data transmission system where data units are received, checked for errors, and retransmitted if errors are detected such that a set of data units is generated, the present invention performs a first reconstruction operation on alternate data units in the sequence and a second reconstruction operation on the other data units in the sequence in order to reconstruct an acceptable data unit. One of the reconstruction operations may include determining a majority voted data unit based on a currently received data unit and previously received data units in the sequence. The other reconstruction operation may perform a direct comparison of the majority voted data to a currently received data unit to identify those bit positions which have different bit values. One or more bit values at those bit positions are changed in the hope of generating a correct data unit. This alternate application of voting and packet comparison reconstruction techniques to a pure automatic repeat request (ARQ) environment (i.e., one without forward error correction) is very significant because a communication unit can significantly improve its performance in high bit error rate environments and increase the probability of correctly receiving a transmitted packet in shorter time periods.
In the preferred example embodiment using alternate majority vote and packet comparison data unit reconstruction techniques, majority voting is less effective when there are an even number of packets in the vote in the sense that it is difficult to resolve "tie" votes. For example, if there are four packets being voted, what value should be assigned to a bit position where two of the packets have "1's" for that bit position and the other two packets have "0's" for that bit position? Rather than arbitrarily selecting a "1" or "0", the preferred example embodiment of the present invention uses a majority vote only for odd numbers of received data packets and direct comparison of the currently received data packet to the majority voted data packet for evenly numbered packets to avoid this tie-breaking dilemma. In both the majority vote and direct comparison techniques, information from previously received data packets is used which increases the likelihood of obtaining a correct packet.
Because the majority vote and direct comparison operations are relatively simple to perform, relatively small amounts of data processing resources and time are consumed. Moreover, the present invention provides a novel technique of making use of information contained in previously received but nonetheless erroneous packets with minimal memory. While the information from previously received erroneous packets is preserved, the packets themselves are not stored. Instead, the present invention accumulates for each corresponding bit position in the reconstructed data packet a sum of bits in that bit position from each received data unit. A threshold is then determined based on the number of retransmitted data units in the sequence, and each accumulated sum is compared to the threshold. If the accumulated sum is less than or equal to the threshold, the bit value for the corresponding bit position of the reconstructed data packet is set to 0. Otherwise, the bit value for the corresponding bit position of the reconstructed data packet is set to 1.